Union Find
Union–Find
別名: Disjoint-set forest (素集合森), 素集合データ構造
Operations
有限集合のdisjointな(互いに共通部分のない)部分集合族を管理する．
空間計算量$ \Theta(n)
$ \alpha(n) は実用上定数と見なせる関数。定義は Summary を参照。
$ \mathtt{unite}(x, y)
$ xが属する集合と$ yが属する集合を結合する
時間計算量$ \Omicron(\alpha(n))\ \mathrm{amortized}
$ \mathtt{same}(x,y)
$ xと$ yが同じ集合に属するか判定する
時間計算量$ \Omicron(\alpha(n))\ \mathrm{amortized}
$ \mathtt{root}(x)
$ xが属する集合を表す根付き木の頂点を返す
時間計算量$ \Omicron(\alpha(n))\ \mathrm{amortized}
$ \mathtt{size\_of}(x)
$ xが属する集合の要素数を返す
時間計算量$ \Omicron(\alpha(n))\ \mathrm{amortized}
Summary
https://gyazo.com/cc7680dff5ccbf97be2ffb8ee38c5386
同じ部分集合に属する$ \iff同じ木に属する となるような森を作り，根を部分集合の代表として諸操作を行う．
$ \mathtt{unite}
https://gyazo.com/bad11d01aafc4713779873d315cb5abe
どちらかの根の親をもう一方の根にする．$ \mathtt{rank}か$ \mathtt{size}によるマージテク(Weighted Union Heuristics?)を行う．
$ \mathtt{root}
https://gyazo.com/7d692bd515c93d8ca11410a3382dd133
根まで頂点をたどる．計算時に使った頂点の親を変更することで木全体の高さを抑える．path compressing, path halving, path splittingなどの変更方法がある．(図はpath compressing)
$ \alpha(n)について
アッカーマン関数$ A(i,j)
$ A(1,j):=2^j \quad (j\ge 1)
$ A(i,1):=A(i-1,2) \quad (i \ge 2)
$ A(i,j) := A(i-1,A(i,j-1)) \quad (i,j \ge 2)
アッカーマン関数の逆関数$ \alpha(m,n)
$ \alpha(m,n):=\min\{i\ge 1 \mid A(i,\lfloor m/n \rfloor) > \log n\}
$ \alpha(n) := \alpha(n,n)
$ m個のfindクエリと$ n個のuniteクエリを処理するときの計算量は$ \Omicron(n + m\alpha(m+n,n))
$ \Omicron(\alpha(n)), \Omicron(\log^* n), \Omicron(\log n)の順に重くなる
$ \log^* n := \begin{cases} 0 & n \le 1 \\ 1 + \log^* (\log n) & n > 1 \end{cases}
$ \log^* 2^{65536} = 5
なので、実用上$ \alpha(n)<5と考えて差し支えない
可換モノイド$ (S,\oplus)を乗せられる
$ \mathtt{unite}時に演算$ \oplusを行うことで、素集合$ Cに対して$ \oplusを適用した結果を求めることができる
つまり$ \bigoplus x_k \quad (x_k \in C)を求められる
集合を分割させないため逆元が必要ない
例えば$ (\N, \min),(\N_0,\gcd),(\N,\mathrm{lcm})
References
Complexity
Dynamic connectivity
Notes
経路圧縮のみ・ランクのみ$ \Omicron(\log n)\ \mathrm{amortized}
経路圧縮とランクを組み合わせると$ \Omicron(\alpha(n))\ \mathrm{amortized}
Implementations
Applications
連結成分の検出: 幅優先探索に比べて$ \mathrm{amortized}\ \Omicron(\alpha(n))重い
閉路の存在判定
Kruskal's algorithm (Minimum Spanning Tree)
分割クエリのみ: クエリを逆から見る
ポテンシャル付きUnion-Find
永続Union-Find
Problems
Verify 用